package com.shm.leetcode;

/**
 * 实现队列
 * 请参照课程内容，用循环数组或者链表实现一个队列，包括：
 *
 * push(int n) - 在队尾插入新元素 n，无需返回
 * pop() - 队首出队
 * front() - 获取队首元素
 * size() - 获取队列大小
 * 题目保证所给操作均合法。
 *
 * 示例：
 *
 *
 * 输入：
 * ["LCQueue", "size", "push", "front", "push", "front", "size", "pop", "front", "pop", "size"]
 * [[], [], [52], [], [22], [], [], [], [], [], []]
 * 输出：
 * [null,0,null,52,null,52,2,null,22,null,0]
 * 解释：
 * LCStack l = LCQueue()
 * l.size()        // 获取队列长度，此时栈为空，返回 0
 * l.push(52) // 放入新元素 52，返回 null
 * l.front()    // 当前队首为 52，返回 52
 * l.push(22)        // 放入新元素 22，返回 null
 * l.front() // 当前队首仍然为 52，返回 52
 * l.size()        // 获取队列长度，返回 2
 * l.pop()         // 52 出队
 * l.front()      // 当前队首为 22，返回 22
 * l.pop()     // 22 出队
 * l.size()    // 当前队列长度为 0
 *
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/high-frequency-algorithm-exercise/xyph5t/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
class LCQueue {
    private int size;
    private Node head;
    private Node tail;

    public LCQueue() {
        size = 0;
        head = tail = new Node(0);
    }

    public void push(int x) {
        tail.next = new Node(x);
        tail.next.prev = tail;
        tail = tail.next;
        size++;
    }

    public void pop() {
        if(head.next.next != null) {
            head.next.next.prev = head;
            head.next = head.next.next;
        } else {
            // 删除前只剩1个元素
            tail = head;
            head.next = null;
        }
        size--;
    }

    public int size() {
        return size;
    }

    public int front() {
        return head.next.value;
    }

    private static class Node {
        int value;
        Node prev;
        Node next;

        public Node(int value) {
            this.value = value;
        }
    }
}

//作者：liberg
//链接：https://leetcode-cn.com/leetbook/read/high-frequency-algorithm-exercise/xyph5t/?discussion=LAOAey